package Other;

public class CircularListInsert {
	public static void main(String[] args) {
		//Create a circular linked list.
		Node head = new Node(1, null);
		head.setNext(new Node(3, null));
		Node original = head;
		head = head.getNext();
		head.setNext(new Node(4, null));
		head = head.getNext();
		head.setNext(new Node(7, null));
		head = head.getNext();
		head.setNext(new Node(8, null));
		head = head.getNext();
		head.setNext(new Node(9, null));
		head = head.getNext();
		head.setNext(new Node(12, original));
		
		head = Insert(head, 77);
		head = Insert(head, 5);
		head = Insert(head, 7);
		head = Insert(head, -3);
		head = Insert(head, 0);
		head = Insert(head, 15);
		
		for(int i = 0; i < 30; i++)
		{
			System.out.println(head.getValue());
			head = head.getNext();
		}
	}
	
	public static Node Insert(Node head, int value)
	{
		Node prev = head;
		Node orig = head;
		Node max = head;
		Node minPrev = head;
		Node min = head;
		
		while(!head.getNext().equals(orig))
		{
			if(value >= head.getValue() && value <= head.getNext().getValue())
			{
				Node temp = new Node(value);
				temp.setNext(head.getNext());
				head.setNext(temp);
				
				return head;
			}
			
			if(head.getValue() > max.getValue())
			{
				max = head;
			}
			
			else if(head.getValue() < min.getValue())
			{
				minPrev = prev;
				min = head;
			}
			
			prev = head;
			head = head.getNext();
		}
		
		if(value > max.getValue())
		{
			Node temp = new Node(value);
			temp.setNext(max.getNext());
			max.setNext(temp);
			
			return temp;
		}
		else if(value < min.getValue())
		{
			Node temp = new Node(value, min);
			minPrev.setNext(temp);
			
			return temp;
		}
		
		return head;
	}
}